package com.dyz.leetcode._13_binaryTree;

import com.dyz.leetcode.TreeNode;

import java.util.*;

public class _102_levelOrder {
    //队列
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root==null){return res;}
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            //每轮循环遍历处理一层节点
            int size = queue.size();
            List<Integer> listLevel = new ArrayList<>();
            for(int i=0; i<size; i++){
                TreeNode curr = queue.poll();
                listLevel.add(curr.val);
                if(curr.left!=null){queue.add(curr.left);}
                if(curr.right!=null){queue.add(curr.right);}
            }
            res.add(listLevel);
        }
        return res;
    }
    //前序遍历
    private class Node{
        TreeNode node;
        int level;

        Node(TreeNode node, int level){
            this.node = node;
            this.level = level;
        }
    }
    public List<List<Integer>> levelOrder2(TreeNode root) {
        List<List<Integer>> res = new ArrayList<>();
        if(root==null){return res;}
        Stack<Node> stack = new Stack<>();
        stack.push(new Node(root, 0));
        while (!stack.isEmpty()){
            Node node = stack.pop();
            TreeNode curr = node.node;
            int currLevel = node.level;
            if(res.size()==currLevel){
                List<Integer> levelNodes = new ArrayList<>();
                res.add(levelNodes);
            }
            res.get(currLevel).add(curr.val);
            if(curr.right!=null){
                stack.push(new Node(curr.right, currLevel+1));
            }
            if(curr.left!=null){
                stack.push(new Node(curr.left, currLevel+1));
            }
        }
        return res;

    }

    //前序遍历改为递归
    private List<List<Integer>> res = new ArrayList<>();
    public List<List<Integer>> levelOrder3(TreeNode root) {
        preOrder(root, 0);
        return res;

    }

    private void preOrder(TreeNode root, int currLevel){
        if(root==null){return;}
        if(res.size()==currLevel){
            List<Integer> levelNodes = new ArrayList<>();
            res.add(levelNodes);
        }
        res.get(currLevel).add(root.val);
        preOrder(root.left, currLevel+1);
        preOrder(root.right, currLevel+1);
    }

    public List<Integer> levelOrder1(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if(root==null){return res;}
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()){
            TreeNode curr = queue.poll();
            res.add(curr.val);
            if(curr.left!=null){queue.add(root.left);}
            if(curr.right!=null){queue.add(root.right);}

        }
        return res;

    }


}
